package leetcode.solution;

/**
 *
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 *
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
 *
 * 示例 1:
 *
 * 输入: [1,2,3,1]
 * 输出: 4
 * 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 *      偷窃到的最高金额 = 1 + 3 = 4 。
 * 示例 2:
 *
 * 输入: [2,7,9,3,1]
 * 输出: 12
 * 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
 *      偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 */
public class 偷窃最高金额 {

    // 是否已偷 true 偷 false 未偷
    private static boolean[] m;
    private static int max;
    private static int tmp;

    /**
     *
     * @param nums
     * @param num 起点
     */
    private static void dfs(int[] nums, int num){
        if (num > nums.length-1){
            return;
        }
        for (int i = num; i < nums.length;i++){
            // 标记位置
            int z = i+1;
            if (!m[z-1] && !m[z+1] && !m[z]){
                m[z] = true;
                tmp += nums[i];
                if (tmp > max){max = tmp;}
                dfs(nums, i+1);
                tmp -= nums[i];
                m[z] = false;
            }
        }
    }

    /**
     * dfs 时间复杂度过高
     * @param nums
     * @return
     */
    public static int rob(int[] nums) {
        m = new boolean[nums.length+2];
        for (int i = 0; i <= nums.length+1; i++){
            m[i] = false;
        }
        max = 0;
        dfs(nums, 0);
        return max;
    }

    /**
     * 最简单的动态规划，最简状态即为nums[0], 状态转移条件为 偷取n+dp[n-2]所获金钱是否大于dp[n-1]
     */
    public static int rob_solu(int[] nums) {
        int pre = 0;
        int sum = 0;
        int tmp = 0;
        for (int i : nums){
            tmp = sum;
            if (i+pre > sum){
                sum = i+pre;
                pre = tmp;
            }else {
                pre = tmp;
            }
        }
        return sum;
    }

    public static void main(String[] args){
        System.out.println(rob_solu(new int[]{2,7,9,3,1}));
    }
}
